'''
@author: Kevin Zhao
@date: Jan 7,2013
'''

'''
Static Stack implemented with a normal array
'''
from linked_list import SinglyLinkedList
class ArrayStack:
    top = -1
    array = []
    def push(self, x):
        if self.top >= len(self.array) - 1:
            print 'stack overflows'
            return None
        self.top += 1
        self.array.insert(self.top, x)
        
    def pop(self):
        if self.top < 0:
            print 'stack underflows'
            return None
        result = self.array[self.top]
        self.top -= 1
        return result
'''
Two stacks within a static array
Exercise 10.1-2
'''
class DualArrayStack:
    array = []
    top_1=-1
    top_2=-1
    def __init__(self, values=None):
        self.top_1 = -1
        self.array = [0] * values #create a array of initial capacity
        self.top_2 = len(self.array)
        
    def push2FirstStack(self, x):
        if self.top_1 + 1 == self.top_2:
            print 'stack overflows'
            return None
        self.top_1 += 1
        self.array[self.top_1] = x
    
    def popFirstStack(self):
        if self.top_1 < 0:
            print 'stack underflows'
            return None
        result = self.array[self.top_1]
        self.top_1 -= 1
        return result
    
    def push2SecondStack(self, x):
        if self.top_2 - 1 == self.top_1:
            print 'stack overflows'
            return None
        self.top_2 -= 1
        self.array[self.top_2] = x
        
    def popSecondStack(self):
        if self.top_2 > len(self.array) - 1:
            print 'stack underflows'
            return None
        result = self.array[self.top_2]
        self.top_2 += 1
        return result
    
        
'''
Dynamic Stack implemented with a singly linked list
Exercise 10.2-2
'''
class SinglyLinkedStack:
    top = -1
    linked_list = SinglyLinkedList()
    def push(self, x):
        self.linked_list.insert(x)
        self.top +=1 
    def pop(self):
        if self.top == -1:
            print 'empty stack'
            return None
        result_value = self.linked_list.deleteByIndex(self.top)
        self.top-=1
        return result_value
'''
Dynamic Stack implemented with a doubly linked list
'''
class DoublyLinkedStack:
    top = None
    def push(self, x):
        return
    def pop(self):
        return
